Practice Problems and Solutions

You should do these problems on paper or mentally first, and only THEN check the solution.

Context-free grammars, parse trees, and ambiguity.

For the following languages, give the strings indicated. You may leave off quote marks for simplicity. The ordering of the strings is just to simplify checking solutions, and is not an essential part of the problem (don't fret about it).

7.1. The language { a^k b a^k | for k ≥ 1 } (just give the first 5 strings).

Show Solution

7.2. The language generated by the grammar (list all strings of length ≤ 5):

	S := a S a 
	S := b S b
	S := c
	S := d

7.3. The language generated by the grammar (list all strings of length ≤ 4):

	S := A B 
	A := a A
	A := c
	B := B b
	B := d
	

7.4. The language generated by the grammar (list all strings of length ≤ 5):

	S := A  
	A := a A a
	A := B
	B := b B b
	B := c
	

7.5. The language generated by the grammar (list all strings of length ≤ 7):

	S := A 
	S := B 
	A := a A bb
	A := a
	B := aa B b
	B := b
	

Problem 7.6 -- 7.9 are not relevant for Midterm 2 in Spring 2019.

7.6. Give a CFG corresponding to the regular expression (a (bb|cc) b)* a

Show Solution

	S := A 
	A := a B b A
	A := a 
	B := bb
	B := cc

7.7. For which of the regular expressions given in Part 1 would it be possible to construct a CFG generating the same language?

Show Solution

7.8. Give a regular expression representing the same language as the CFG in problem 2.3.

Show Solution

7.9. For which of the grammars in problems 2.2 - 2.5 would it be possible to find a regular expression representing the same language?

Show Solution

The following problem is designed to go with material on finite-state automata, but can be solved without it!

7.10. Give a CFG generating the language over {a,b}* with an even number of a's and an odd number of b's Hint: draw an automaton first, then write a grammar which has a non-terminal for each state; you may need to use erasing rules of the form A := ε.

Show Solution

	S := A 
	A := a B
	A := b C 
	B := b D
	B := a A
	C := a D 
	C := b A
	D := a C
	D := b B
	C := ε

For the following grammars and string s, give (a) a parse tree (b) a left-most derivation, and (c) a right-most derivation.

7.11.

	S := A B 
	A := a A
	A := c
	B := B b
	B := d
	

Show Solution

(a) 

(b) S => AB => aAB => aaAB => aacB => aacBb => aacdb
(c) S => AB => ABb => Adb  => aAdb => aaAdb => aacdb

7.12.

	S := E
	E := a
	E := [ L ] 
	E := []
	L := E , L
	L := E
	

Show Solution

(a) 

(b) S => E => [ L ] => [ E , L ] => [ a , L ] => [ a , E ] => [ a , [ L ] ] => [ a , [ E ] ] => [ a , [ a ] ]
(c) S => E => [ L ] => [ E , L ] => [ E , E ] => [ E , [ L ] ] => [ E , [ E ] ] => [ E , [ a ] ] => [ a , [ a ] ]

7.13.

    S := E
    E := E + T 
    E := T 
    T := T * F 
    T := F 
    F := - F 
    F := F1 
    F1 := F2 ** F1
    F1 := F2
    F2 := a
	

Show Solution

(a) 

(b) S => E + T => T + T => F + T => F1 + T => F2 + T => a + T 
      => a + F => a + -F => a + -F1 => a + - F2 ** F1 => a + - a ** F1 => a + - a ** F2 => a + - a ** a
(c) S => E + T => E + F => E + - F => E + -F1 => E + - F2 ** F1 => E + - F2 ** F2 
      => E + - F2 ** a => E + - a ** a => a + - a ** a

7.14.

    S := E
    E := E + T 
    E := T 
    T := T * F 
    T := F 
    F := - F 
    F := a
	

Show Solution

(a)
 
(b) S => E => E + T => T + T => T * F + T => F * F + T => a * F + T
      => a * a + T => a * a + F => a * a + -F => a * a + -a
(c) S => E => E + T => E + F => E + -F => E + -a => T + -a 
      => T * F + -a => T * a + -a => a * a + -a

For the following CFGs, state whether or not they are ambiguous, and if ambiguous, give two different left-most derivations for some string OR two different parse trees.

7.15.

    S := A
    A := a A
    A := B
    B := a B
    B := a

 
    S => A => aA => aB => aa 
    S => A => B => aB => aa

7.16.

    S := A
    A := a A b
    A := a A
    A := b

Ambiguous!  aabb has two parse trees (thanks to Sho Nihei for noticing this!):
           S
           |
           A
         / | \
        a  A  b
         /   \
        a     A
              |
              b
and

           S
           |
           A
         /   \
        a     A
            / | \
           a  A  b
              |
              b      

7.17. (This grammar attempts to generate the language with an equal number of a's and b's.)

    S := A                     
    A := a A b
    A := b A a
    A := A A
    A := a b
    A := b a 

Show Solution

 
    S => A => aAb => abab 
    S => A => AA => abA => abab

7.18. (The language of matching parentheses.)

    S := A                     
    A := ( A )
    A := A A
    A := ()

Show Solution

 
    S => A => A A => ()A => ()AA => ()()A => ()()()
    S => A => A A => AAA => ()AA => ()()A => ()()()

Answer the following two questions.

7.19. Write a CFG that represents the same language as the CFG in problem 7.15, but is NOT ambiguous.

Show Solution

 
    S := a S
    S := a

7.20. Write a CFG that represents the same language as the CFG in problem 7.18, but is NOT ambiguous.

Show Solution

 
    S := A
    A := A B            # this generates a sequence of B's
    A := B
    B := ( A )          # this generates the nested parentheses
    B := ()